/*
题目链接 : https://leetcode.cn/problems/zero-array-transformation-iv/description/
*/

//题解代码 :
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& que) {
        int n = nums.size(),m = que.size();

        vector<vector<int>> f(2,vector<int>(1001));
        auto check = [&](int i)->int{
            int l=0,r=m;
            while(l<=r){
                int mid = (l+r)/2;
                fill(f[0].begin(),f[0].end(),0);
                fill(f[1].begin(),f[1].end(),0);
                int old = 0,cur = 1;
                f[old][0] = 1;
                for(int j=1;j<=mid;++j){
                    int jl = que[j-1][0],jr = que[j-1][1], jval = que[j-1][2];
                    for(int v=0;v<=nums[i];++v){
                        f[cur][v] = f[old][v];
                        if(i>=jl && i<=jr && v>=jval){
                            f[cur][v] = max(f[cur][v],f[old][v-jval]);
                        }
                    }
                    old^=1,cur^=1;
                }
                if(f[old][nums[i]]) r = mid - 1;
                else l = mid + 1;
            }
            return l;
        };

        int ans = 0;
        for(int i=0;i<n;++i){
           ans = max(ans,check(i));
        }
        return ans == m+1 ? -1 : ans;
    }
};
